home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / protect.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-23  |  13.9 KB  |  429 lines
  1. /*-----------------------------------------------------------------------------
  2. Update board
  3.  
  4. Revision History
  5. ----------------
  6. Gary Culp   3-14 Dec 1988  Initial version.
  7. Gary Culp   19 Dec 1988    Added prot_check_flag to handle_changed_pieces, so
  8.                            that the display routines can use it, too.
  9. -----------------------------------------------------------------------------*/
  10.  
  11. /*
  12. Glossary terms:        ***!!!
  13.    permanent  (piece)
  14.    axis
  15.    hostile    (piece or color)
  16.    friendly   (piece or color)
  17.    off-board  (piece or color)
  18.  
  19. A common piece of advice to Othello players is to take the corners of the
  20. board, because they can never be captured from you.  Not only can you depend
  21. upon their contributing to your final count of pieces, they make a good
  22. solid foundation upon which to build.  Something I haven't heard pointed out
  23. though, is that corners aren't the only pieces that can't be captured.
  24. I call any piece that can't be captured a permanent piece.  My strategy when
  25. playing Othello is to acquire as many permanent pieces as I can; and that is
  26. the strategy implemented in this game.  The most challenging part of this
  27. project, for me, was figuring out an efficient algorithm for determining which
  28. pieces in a given board configuration are permanent.  The answer was obvious
  29. (after several hours of intense thought :) ).
  30. This file contains the code which implements the algorithm.
  31.  
  32. To capture a piece (or line of pieces), P, the opponent must place 
  33. his pieces, O, on opposite sides of P.
  34. There are 4 axes through which this may be done:
  35.  
  36. horizontal   vertical   forward    backward
  37.                         diagonal   diagonal
  38.                O             O      O
  39.  O P O         P           P          P
  40.                O         O              O
  41.  
  42. If a piece is protected from being captured along all 4 axes, it cannot be
  43. captured at all, and is therefore permanent.
  44.  
  45. A piece is protected along an axis if one of these conditions is true:
  46.  
  47. 1)  The axis is full.
  48. 2)  One of the adjacent pieces along the axis is a friendly permanent piece.
  49. 3)  Both of the adjacent pieces along the axis are permanent.  (It doesn't
  50.     matter what colors they are.)
  51.  
  52. For these rules for protection along an axis to work, we have imaginary
  53. squares which lie off the edge of the board (that's why the boards are
  54. manipulated as 10x10 instead of 8x8).  These imaginary squares contain
  55. permanent pieces of a third color: "off-board".  Off-board is considered
  56. to be a friendly color, for both players.  It may seem weird to add all
  57. this imaginary stuff to the game, but it greatly simplifies handling the
  58. edge of the board.  Off-board pieces make the code simpler, smaller,
  59. and faster, at the expense of making the board data structure larger.
  60.  
  61. When to check protection and permanence:
  62.  
  63.    When a piece is played or its color is changed, all 4 of its axes must be
  64.    checked for protection (previous protection may be invalidated by color
  65.    change).
  66.  
  67.    When a protection bit that was clear is set, the piece must be checked
  68.    for permanence.
  69.  
  70.    When a piece becomes permanent, the pieces adjacent to it must be checked
  71.    for protection along the axis containing the newly permanent piece.
  72. */
  73.  
  74.  
  75. #include "othello.h"
  76.  
  77.  
  78. /* These definitions aren't used anywhere else.  They are part of a trick
  79.    for determining whether the protected axis rules are satisfied. (The
  80.    rules which deal with adjacent pieces being permanent, not the rule
  81.    about a full axis.)
  82.    Note that TRICK_PROTECTED == TRICK_ADJ1_PERM | TRICK_ADJ2_PERM.
  83. */
  84. #define TRICK_ADJ1_PERM    1 
  85. #define TRICK_ADJ2_PERM    2
  86. #define TRICK_PROTECTED    3
  87.  
  88. /*--------------------------------*/
  89. /*          Prototypes            */
  90. /*--------------------------------*/
  91.  
  92. void handle_changed_pieces(
  93.    struct board_struct *board_ptr,
  94.    int *affected_list,
  95.    int num_affected,
  96.    unsigned char new_color,
  97.    int prot_check_flag);
  98.  
  99. void new_piece_axis_fill_check(
  100.    struct board_struct *board_ptr,
  101.    int *affected_list);
  102.  
  103. void perform_all_protection_checks(struct board_struct *board_ptr);
  104.  
  105. unsigned char is_filled_axis(unsigned char *new_piece_ptr, int axis_num);
  106.  
  107. void request_prot_check(
  108.    struct board_struct *board_ptr, /* pointer to board structure */
  109.    unsigned char *cell_ptr,        /* pointer to cell */
  110.    unsigned char requested_axes);  /* requesting prot check for these axes */
  111.  
  112. int next_check(int *row_num_ptr, int *clm_num_ptr, int *axis_num_ptr);
  113.  
  114. /*--------------------------------*/
  115. /*             Variables          */
  116. /*--------------------------------*/
  117.  
  118. /* To convert axis flags to axis numbers, shift the axis flag right 4 bits;
  119.    use the result as an index into this table.
  120. */
  121. static const unsigned char bit_priority_encode[] = {
  122.    0, /* [0000] */ /* actually, no bit set */
  123.    0, /* [0001] */
  124.    1, /* [0010] */
  125.    1, /* [0011] */
  126.    2, /* [0100] */
  127.    2, /* [0101] */
  128.    2, /* [0110] */
  129.    2, /* [0111] */
  130.    3, /* [1000] */
  131.    3, /* [1001] */
  132.    3, /* [1010] */
  133.    3, /* [1011] */
  134.    3, /* [1100] */
  135.    3, /* [1101] */
  136.    3, /* [1110] */
  137.    3, /* [1111] */
  138. };
  139.  
  140. /*
  141.    For movement along an axis within a board, add or subtract
  142.    delta_array[axis_number] to a pointer to a cell within the board.
  143. */
  144. const int delta_array[4] = {11, 9, 1, 10};
  145.  
  146. static unsigned char schedule_map[10][10];
  147.  
  148.  
  149. /*------------------------------*/
  150. /*           Functions          */
  151. /*------------------------------*/
  152.  
  153.  
  154. /*
  155. Given a list of affected pieces, starting with the new piece,
  156. update the board, including the protection flags.
  157. */
  158. void
  159. update_protection_for_board(
  160.    struct board_struct *board_ptr,
  161.    int *affected_list, /* list of affected pieces, beginning with new piece */
  162.    int num_affected,   /* number of pieces in affected list */
  163.    unsigned char new_color)   /* new color for affected pieces */
  164. {
  165.    handle_changed_pieces(board_ptr, affected_list, num_affected, new_color, 1);
  166.    new_piece_axis_fill_check(board_ptr, affected_list);
  167.    perform_all_protection_checks(board_ptr);
  168. }
  169.  
  170. /*
  171. Update board according to list of pieces changed by this move (including
  172. new piece).
  173. */
  174. void
  175. handle_changed_pieces(
  176.    struct board_struct *board_ptr,
  177.    register int *affected_list, /* list of affected pieces, beginning with new piece */
  178.    int num_affected,            /* number of pieces in affected list */
  179.    unsigned char new_color,     /* new color for affected pieces */
  180.    int prot_check_flag)         /* flag: request protection checks iff set */
  181. {
  182.    register unsigned char *cell_ptr;
  183.  
  184.    /* for all pieces changed by the move, including the new piece */
  185.    while (num_affected--) {
  186.  
  187.       /* Clear all protection bits for this piece & set its new color. */
  188.       *(cell_ptr = &board_ptr->board[0][0] + *affected_list++) = new_color;
  189.  
  190.       /* Request that this piece be checked for protection along all 4 axes. */
  191.       if (prot_check_flag) {
  192.          request_prot_check(board_ptr, cell_ptr, BD_AX | FD_AX | H_AX | V_AX);
  193.       }
  194.    }
  195. }
  196.  
  197. /*
  198. Check each axis of new piece to see if we filled the axis.
  199. */
  200. void
  201. new_piece_axis_fill_check(
  202.    struct board_struct *board_ptr,
  203.    int *affected_list) /* list of affected pieces, beginning with new piece */
  204. {
  205.    unsigned char axis_flag;
  206.    unsigned char *new_piece_ptr;
  207.    register unsigned char *cell_ptr;
  208.    int axis_num;
  209.  
  210.    new_piece_ptr = &board_ptr->board[0][0] + *affected_list;
  211.  
  212.    /* for all 4 axes through the new piece */
  213.    for (axis_num = BD_NDX; axis_num <= V_NDX; axis_num++) {
  214.       if (is_filled_axis(new_piece_ptr, axis_num)) {
  215.  
  216.          /* Set full-axis bit for this axis */
  217.          SET_FA_BIT(board_ptr->fa_bits,
  218.           fa_tabl[*affected_list / 10 - 1][*affected_list % 10 - 1][axis_num]);
  219.  
  220.          /* Request protection check for each piece along this axis.
  221.             (The pieces are protected along this axis, of course.
  222.             But it's easier to keep the protection checking in one place,
  223.             so we go through the scheduler.)
  224.  
  225.             The loop which does this (below) never hits the new piece, but
  226.             that's OK because we already requested that it be checked for
  227.             protection (It's in the affected_list).
  228.          */
  229.  
  230.          {
  231.             register int delta;
  232.             int pass;
  233.  
  234.             axis_flag = (unsigned char)BD_AX << axis_num;
  235.  
  236.             delta = delta_array[axis_num];
  237.             for (pass = 0; pass < 2; pass++, delta = -delta) {
  238.                cell_ptr = new_piece_ptr;
  239.                while (!(*(cell_ptr += delta) & OFF_BOARD)) {
  240.                   request_prot_check(board_ptr, cell_ptr, axis_flag);
  241.                }
  242.             }
  243.          }
  244.       }
  245.    }
  246. }
  247.  
  248.  
  249. /*
  250.    Perform protection checks until they're all done.
  251.  
  252.    initialize row and column
  253.    while scheduler returns pieces to check {
  254.       check piece for protection along specified axis
  255.       if piece is protected {
  256.          set protection flag
  257.          if piece is permanent {
  258.             schedule adjacent pieces to be checked for permanence along
  259.             the axis containing this piece
  260.          }
  261.       }
  262.    }
  263. */
  264. void
  265. perform_all_protection_checks(struct board_struct *board_ptr)
  266. {
  267.    int row;
  268.    int clm;
  269.    int rule_trick;
  270.    register unsigned char *cell_ptr;
  271.    int axis_num;
  272.  
  273.    row = 1;
  274.    clm = 1;
  275.  
  276.    while (next_check(&row, &clm, &axis_num)) {
  277.  
  278.       cell_ptr = &board_ptr->board[row][clm];
  279.  
  280.       if (CHK_FA_BIT(board_ptr->fa_bits, fa_tabl[row-1][clm-1][axis_num])) {
  281.          /* axis is full, therefore piece is protected along it */
  282.          rule_trick = TRICK_PROTECTED;
  283.       }
  284.       else {
  285.          unsigned char adjac1;
  286.          unsigned char adjac2;
  287.          unsigned char friendly_colors;
  288.  
  289.          friendly_colors = *cell_ptr & (US_PIECE | THEM_PIECE) | OFF_BOARD;
  290.          adjac1 = *(cell_ptr + delta_array[axis_num]);
  291.          adjac2 = *(cell_ptr - delta_array[axis_num]);
  292.  
  293.          rule_trick =
  294.             IS_PERM(adjac1) ?
  295.             (BELONGS(adjac1, friendly_colors) ? TRICK_PROTECTED : TRICK_ADJ1_PERM)
  296.             :
  297.             0 ;
  298.  
  299.          if (IS_PERM(adjac2)) {
  300.             rule_trick |= BELONGS(adjac2, friendly_colors) ?
  301.                TRICK_PROTECTED : TRICK_ADJ2_PERM;
  302.          }
  303.       }
  304.  
  305.       if (rule_trick == TRICK_PROTECTED) {
  306.          /* the piece is protected along this axis */
  307.  
  308.          /* set the protection flag & check for permanence */
  309.  
  310.          if (IS_PERM(*cell_ptr |= BD_AX << axis_num)) {
  311.             int sched_ax_num;
  312.       
  313.             /* Piece is now permanent. */
  314.  
  315.             /* Schedule protection checks for all adjacent pieces
  316.                along the axis containing this piece.
  317.             */
  318.             for (sched_ax_num = BD_NDX;
  319.                sched_ax_num <= V_NDX;
  320.                sched_ax_num++)
  321.             {
  322.                request_prot_check(
  323.                   board_ptr,
  324.                   cell_ptr + delta_array[sched_ax_num],
  325.                   BD_AX << sched_ax_num
  326.                );
  327.                request_prot_check(
  328.                   board_ptr,
  329.                   cell_ptr - delta_array[sched_ax_num],
  330.                   BD_AX << sched_ax_num
  331.                );
  332.                   cell_ptr - delta_array[sched_ax_num];
  333.             }
  334.          }
  335.       }
  336.    }
  337. }
  338.  
  339.  
  340. /*
  341. Set bit(s) in the protection check scheduling map.
  342.  
  343. If the cell is unoccupied, the entire request will be ignored.
  344. Schedule bits corresponding to axes which are already protected
  345.    will not be set.
  346. */
  347. void
  348. request_prot_check(
  349.    struct board_struct *board_ptr, /* pointer to board structure */
  350.    unsigned char *cell_ptr,        /* pointer to cell */
  351.    unsigned char requested_axes)   /* requesting prot check for these axes */
  352. {
  353.    if (BELONGS(*cell_ptr, US_PIECE | THEM_PIECE)) {
  354.       /* Cell is occupied.
  355.          Set bits for requested axes, except those axes
  356.          which are already protected.
  357.       */
  358.  
  359.       *(&schedule_map[0][0] + (cell_ptr - &board_ptr->board[0][0]))
  360.          |= requested_axes & ~*cell_ptr;
  361.    }
  362.    /* else cell is unoccupied, so ignore request */
  363. }
  364.  
  365. /*
  366. Get next cell for protection check
  367.  
  368. Returns:
  369.    0: no more cells need to be checked
  370.    1: cell at *row_num_ptr, *clm_num_ptr needs to be checked along axis
  371.       number *axis_num_ptr
  372. */
  373. int
  374. next_check(int *row_num_ptr, int *clm_num_ptr, int *axis_num_ptr)
  375. {
  376.    register unsigned char *p;
  377.    register unsigned char *stop;
  378.    unsigned char *start;
  379.    int temp;
  380.    int pass;
  381.  
  382.    p = start = &schedule_map[*row_num_ptr][*clm_num_ptr];
  383.    stop = &schedule_map[8][9];
  384.    for (pass = 0; pass < 2; pass++) {
  385.       while (*p == 0 && ++p < stop) ;
  386.       if (p != stop) {
  387.          /* found one, perform calcs and return */
  388.          temp = p - &schedule_map[0][0];
  389.          *row_num_ptr = temp / 10;
  390.          *clm_num_ptr = temp % 10;
  391.          /* Determine which axis & clear schedule bit for that axis */
  392.          *p ^= BD_AX << (*axis_num_ptr = bit_priority_encode[*p >> 4]);
  393.          return (1); /* found one */
  394.       }
  395.       p = &schedule_map[1][1]; /* now check from 1st cell of the board... */
  396.       stop = start;            /* ...up to where we started checking */
  397.    }
  398.    return (0); /* they're all done */
  399. }
  400.  
  401.  
  402. /*
  403. Determine whether a specified axis has been filled by a new piece.
  404.  
  405. The cell occupied by the new piece is never checked; it is just assumed
  406. to be occupied.
  407.  
  408. Returns:
  409.    1 if axis is filled, 0 if axis is not filled
  410. */
  411. unsigned char
  412. is_filled_axis(unsigned char *new_piece_ptr, int axis_num)
  413. {
  414.    register unsigned char *ptr;
  415.    register int delta;
  416.    int pass;
  417.  
  418.    delta = delta_array[axis_num];
  419.    for (pass = 0; pass < 2; pass++, delta = -delta) {
  420.       ptr = new_piece_ptr;
  421.       while (*(ptr += delta) & (US_PIECE | THEM_PIECE)) ;
  422.       if (*ptr & NO_PIECE) {
  423.          return (0);    /* This axis is still unfilled. */
  424.       }  /* else we ran off the edge of the board */
  425.    }
  426.  
  427.    return (1);
  428. }
  429.